1.1 Field of the Invention
The present invention relates to methods and apparatuses for signal detection, acquisition and processing. The invention is applicable all types of “signals” and data, including but not limited to signals, images, video and other higher dimensional data.
1.2 Brief Description of the Related Art
1.2.1 Limits of Analog-to-Digital Conversion
The power, stability, and low cost of digital signal processing (DSP) has pushed the analog-to-digital converter (ADC) increasingly close to the front-end of many important sensing, imaging, and communication systems. An ADC converts an analog input waveform to a sequence of quantized, periodic discrete-time samples; a representation justified by the Nyquist/Shannon sampling theorem that states that any bandlimited signal can be completely reconstructed from uniform time samples provided a sampling rate twice the highest frequency in the signal (the Nyquist rate). ADCs are characterized in terms of their sampling rate and the number of bits they use to represent each sample.
There are many applications that severely stress current ADC technologies. For example, consider signal acquisition and processing in the radio frequency (RF) bands. In a radar system, for example, the sampling bandwidth is inversely proportional to the resolution of the radar, and many bits are needed in order to tease weak target signals out from dominating clutter, jammers, and background noise. In signals intelligence, the receiver must surveil a wide RF bandwidth for weak, potentially covert signals of interest in a background of numerous other transmissions and noise; moreover, many bits are needed in order to differentiate among the numerous levels of increasingly complicated signaling constellations. In these settings, current ADC technologies cannot perform at the bit rate and depth required for faithful detection and reconstruction.
Even worse, the current pace of ADC development is incremental and slow. It will be decades before ADCs based on current technology will be fast and precise enough for pressing applications. Even after better ADCs become available, the deluge of data will swamp back-end DSP algorithms. For example, sampling a 1 GHz band at 16 bits-per sample would generate data at rate of 2 GB/s, which would fill a modern hard disk in roughly two minutes. In a typical application, only a tiny fraction of this information is relevant. Thus, it is our contention that incremental advances based on the Nyquist/Shannon sampling theory will be insufficient for many applications. Rather, it is necessary to revise the founding premises of sampling theory.
1.3 Related Work
1.3.1 Analog-to-Digital Converters
The demands of various analog-to-digital (ADC) applications vary from one application to another. Increasing the sampling frequency and increasing the resolution (number of bits) are the challenging tradeoffs for the current ADCs. For applications demanding high sampling frequencies or high data rates, the number of data bits is often sacrificed. For military applications, such as radar signal processing, high sampling frequency and high resolution is mandatory. Hence, designing a high precision ADC for wideband signals is the main goal in order to address such applications.
Flash, pipelined, and sigma delta analog-to-digital converters are the three main implementations of ADCs. Flash ADCs have the advantage of being very fast, as the conversion happens in a single cycle at the cost of the increased area and power consumptions. Each additional bit almost doubles the area and power consumption; a maximum resolution of eight bits is reported for a flash ADC converter at a sampling frequency of 2 GHz. See C. Azzolini, A. Boni, A. Facen, M. Parenti, and D. Vecchi, “Design of a 2-GS/s 8-b Self-Calibrating ADC in 0.18 m CMOS technology,” IEEE International Symposium on Circuits and Systems, ISCAS'05, pages 1386-1389, May 2005. For wideband applications, such as radar and optical communications, multi-GHz sampling is necessary. However, increasing the sampling frequency of the flash ADC converter reduces the effective number of bits dramatically. Previously, for multi-GHz operations, expensive technologies, such as InP—InGaAs, were used to fabricate the wideband flash ADC. However, due to the high sampling frequency, low resolution was obtained. Flash ADC converters with a sampling frequency of 24 GHz with just 3-bits of resolution were reported in Nosaka, M. Nakamura, M. Ida, K. Kurishima, T. Shibata, M. Tokumitsu, and M. Muraguchi, “A 24-Gsps 3-bit Nyquist ADC using InP HBTs for Electronic Dispersion Compensation,” Proceedings of IEEE MIT-S International Microwave Symposium, 1:101-104, June 2004. On the other hand, current CMOS technologies do not support high sampling frequencies, because of the limited transistor cut-off frequency. Nevertheless, a 5 GHz 4-bit flash ADC using 0.18 m technology was reported recently in S. Sheikhaei, S. Mirabbasi, and A. Ivanov, “A 4-Bit 5 GS/s Flash A/D Converter in 0.18 m CMOS,” In IEEE International Symposium on Circuits and Systems, ISCAS'05, pages 6138-6141, May 2005. For higher sampling frequencies, time-interleaved architectures, which are based on flash ADC, are commonly used. In these architectures, a number of lower speed converters, with a minimized input capacitance are placed in parallel. Using time interleaving, a high speed sampling is obtained. Because of the gain and offset mismatches among the different parallel channels and clock jitter, time-interleaved architectures usually require digital calibration methods that significantly increase the power and limits the resolution of the ADC. See W. Ellersick, C. K. Yang, M. Horowitz, and W. Dally, “GAD: A 12 GS/s CMOS 4-bit A/D converter for an equalized multilevel link,” IEEE Symposium on VLSI Circuits, Digest of Technical Papers, pages 49-52, June 1999; C. K. Yang, V. Stojanovic, S. Mojtahedi, M. Horowitz, and W. Ellersick, “A serial-link transceiver based on 8-G samples/s A/D and D/A converters in 0.25 m CMOS,” IEEE Journal of Solid State Circuits, pages 293-301, November 2001; L. Y. Nathawad, R. Urata, B. A. Wooley, and D. A. B. Miller, “A 40-GHz-Bandwidth, 4-Bit, Time-Interleaved A/D Converter Using Photoconductive Sampling,” IEEE Journal of Solid State Circuits, pages 2021-2030, December 2003; and S. Naraghi and D. Johns, “A 4-bit analog-to-digital converter for high-speed serial links,” Micronet Annual Workshop, pages 33-34, April 2004. To achieve higher resolution than in the case of flash converters, pipelined architectures are commonly used. Conventionally, pipelined ADCs are usually implemented using closed loop circuit design techniques that utilize a multiplying DAC. Due to the delay introduced by the settling time of the DAC, high sampling rates for high resolution ADC is one of the main challenges for pipelined ADC. Resolutions of 16 bits are obtainable for low sampling frequencies using the pipelined architectures, while the resolution reduces to 8 bits as the sampling frequency increases to 400 MHZ. See C. S. G Conoy, “An 8 bit 85 Msps parallel pipeline A/D converter in 1-m CMOS,” IEEE Journal of Solid State Circuits, April 1993; W. Bright “8 bit 75 MSps 70 mW parallel pipelined ADC incorporating double sampling,” Solid State Circuits Conference, February 1998; and Y. Kim, J. Koa, W. Yuu, S. Lim, and S. Kim, “An 8-bit 1 GSps CMOS Pipeline ADC,” IEEE Asia-Pacific Conference on Advanced System Integrated Circuits AP-ASIC2004, pages 424-425, August 2004. Therefore, sub-GHz sampling rates characterize pipelined ADC, and, therefore, pipelined ADCs are not suitable for wideband applications.
Sigma delta ADCs are the most common type of oversampled converters. The main advantage of the sigma delta ADCs is the capability of pushing the quantization noise from the band of interest to other frequency bands (noise shaping), and, thereby, increase the resolution while attaining low power consumption. See E. J. van der Zwan and E. C. Dijkmans, “A 0.2 mW CMOS Modulator for Speech Coding with 80 dB Dynamic Range,” In IEEE International Solid-State Circuits Conference, Digest of Technical Papers, ISSCC, pages 232-233, 451, February 1996; E. J. van der Zwan, K. Philips, and C. A. A. Bastiaansen, “A 10.7-MHz IF-to-baseband A/D conversion system for AM/FM radio receivers,” IEEE Journal of Solid State Circuits, pages 1810-1819, December 2000; K. Philips, “A 4.4 mW 76 dB complex ADC for Bluetooth receivers,” IEEE International Solid-State Circuits Conference (ISSCC), pages 464-478, February 2003; and R. H. M. Van Veldhoven, “A Triple-Mode Continuous-Time Modulator With Switched-Capacitor Feedback DAC for a GSM-EDGE/CDMA2000/UMTS Receiver,” IEEE Journal of Solid State Circuits, pages 2069-2076, December 2003. The oversampling relaxes the requirements of the anti-aliasing filter, and, hence, it could be easily implemented. In addition, using the continuous time architectures of the sigma delta ADC, the anti aliasing filter could be removed due to the inherent anti-aliasing property. However, the main limitations of the sigma delta ADC are the latency and oversampling. Hence, sigma delta ADC is used in applications where resolutions in excess of 10 bits are required while the signal bandwidth is very small compared to the sampling frequency. Increasing the order, oversampling ratio (OSR) or having a multi-bit DAC are the current challenges of sigma delta ADC in order to enhance their performance. The discrete time implementation of sigma delta is based on switched capacitor circuits, and, therefore, the maximum sampling frequency is limited by the opamp cut-off frequency and sampling errors. Sampling frequencies higher than 100 MHz are hard to achieve using the discrete time implementations. On the other hand, continuous time implementations, such as Gm C and passive sigma delta, support higher sampling requirements. However, continuous time implementations are limited by the excess loop delay, sampling jitter and non linearity of the used analog circuits.
Current research efforts are focusing on finding new circuit techniques and modifying existing architectures for solving technology related problems, such as non-linearities, clock jitter, and noise, in order to enhance the performance (increase the sampling frequency) of the ADC. On the other hand, our approach provides an innovative theory for building high performance ADC without the requirement of increasing the sampling frequency and it allows the use of the existing technology to build high performance ADCs.
1.3.2 Compressed Sensing
Over the past decades the amount of data generated by sensing systems has grown from a trickle to a torrent. This has stimulated much research in the fields of compression and coding, which enable compact storage and rapid transmission of large amounts of information. Compression is possible because often we have considerable a priori information about the signals of interest. For example, many signals are known to have a sparse or compressible representation in some transform basis (Fourier, DCT, wavelets, etc.) and can be expressed or approximated using a linear combination of only a small set of basis vectors.
The traditional approach to compressing a sparse signal is to compute its transform coefficients and then store or transmit the few large coefficients and their locations. This is an inherently wasteful process (in terms of both sampling rate and computational complexity), since it forces the sensor to acquire and process the entire signal even though an exact representation is not ultimately required. For instance, in many signal processing applications (including most communications and many radar systems), signals are acquired only for the purpose of making a detection or classification decision.
A new framework for simultaneous sensing and compression has developed recently under the rubric of Compressed Sensing (CS). Donoho and, independently, Candès, Romberg, and Tao have put forth this framework in the following series of papers:                D. Donoho, “Compressed sensing,” IEEE Trans. Information Theory, Preprint, 2004;        E. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,” Preprint, 2004;        D. Donoho, “High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension,” Preprint, 2005;        D. Donoho, “Neighborly polytopes and sparse solutions of underdetermined linear equations,” 2005, Preprint;        E. Candès and T. Tao, “Near optimal signal recovery from random projections and universal encoding strategies,” IEEE Trans. Information Theory, 2004, Submitted;        E. Candès and T. Tao, “Decoding by linear programming,” IEEE Trans. Information Theory, Preprint, 2005; and        E. Candès, J. Romberg and T. Tao, “Stable Signal Recovery from Incomplete and Inaccurate Measurements”, Preprint, 2005This series of work has enjoyed considerable recent attention.        
CS enables a potentially large reduction in the sampling and computation costs at a sensor. CS relies on the concept that a signal having a sparse representation in one basis can be reconstructed from a small set of projections onto a second, measurement basis that is incoherent with the first. (Roughly speaking, incoherence means that no element of one basis has a sparse representation in terms of the other basis.) Interestingly, random projections are a universal measurement basis in the sense that they are incoherent with any other fixed basis with high probability. The CS measurement process is nonadaptive; the reconstruction process is nonlinear. A variety of reconstruction algorithms have been proposed; see E. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information”, Preprint, 2004, D. Donoho, “Compressed sensing”, Preprint, 2004, and J. Tropp and A. C. Gilbert, “Signal recovery from partial information via orthogonal matching pursuit”, Preprint, April 2005.
Reinterpreting their work in view of the theory of optimal recovery (discussed below), one finds that CS strives to recovery the signal identically. The signal statistics that CS computes are strictly the identity (or, in some situations, an orthogonal transformation of the signal). The algorithmic framework that CS employs involves linear programming and convex optimization. If we define signal recovery or information extraction to be exact, full recomputation of the original signal, then CS performs admirably. The CS recovery algorithm outputs a signal whose error matches the error rate for the input signal class.
There are situations in which we wish to reconstruct the signal exactly. Image processing and medical imaging, in particular, are two such applications. In medical imaging applications, we may be able to make a few measurements of a person, a piece of tissue, or an experimental subject and recovery or generate a full image of the object in question using the CS algorithms and framework. Medical professionals and diagnosticians are highly trained at reading full, specific images from such devices and we simply cannot present them with a few significant portions of these types of images.
If, however, we wish to extract different types of information other than the identity, then the compressed sensing framework is not applicable. We argue that if a signal is sparse or compressible, as is assumed in CS, then the information present in the signal is those significant transform coefficients only, not the many insignificant ones. Furthermore, we may reconstruct an approximation using only the significant coefficients obtained from reconstruction that produce an error rate equal or better that the rate prescribed by the CS reconstruction theory. We note that an algorithm which only needs to output a few significant transform coefficients should (and often will) run considerably faster than the CS algorithms, which take time to output a signal just as long as the input signal. The greedy algorithms pursued for CS recovery enjoy this dramatic computational advantage over other iterative optimization techniques proposed by Donoho, Candès and Tao, Nowak, and others in D. Donoho, “Compressed sensing,” Preprint, 2005; E. Candès and T. Tao, “Near optimal signal recovery from random projections and universal encoding strategies,” Preprint, 2004; and J. Haupt and R. Nowak, “Signal reconstruction from noisy random projections,” Preprint, 2004. For many applications, the large transform coefficients are the only ones that matter and, for these applications, we need not compute the smaller ones.
In addition, there are many realtime applications for which these smaller coefficients are a luxury we cannot afford to spend time computing. Transform coefficients are but one type of statistics we might wish to compute from the signal. A number of applications might require nonlinear statistics (such as order statistics) or perform a simple classification procedure upon the signal (such as deciding whether or not a recorded signal contains an encoded communication). Compressed Sensing cannot currently address these needs.
Another important aspect of the CS theory is that it is designed for finite-length, discrete-time signals and so is not immediately applicable to analog and streaming signals.
1.3.3 Finite Rate of Innovation Sampling
In M. Vetterli, P. Marziliano, and T. Blu, “Sampling signals with finite rate of innovation,” IEEE Trans. Signal Proc., 50(6), June 2002, Vetterli et al. propose a methodology for sampling signals having a finite rate of innovation. Such signals are modeled parametrically with a finite number of degrees of freedom per unit time; R is deemed the rate of innovation. Examples include streams of delta functions with unknown positions and amplitudes or piecewise polynomial signals with unknown polynomial coefficients and breakpoints. Applications have also been proposed in Ultra Wideband (UWB) communications, where a stream of similar pulses may arrive with different delays and amplitudes. See J. Kusuma, A. Ridolfi, and M. Vetterli, “Sampling of communications systems with bandwidth expansion,” Proc. ICC, 2002.
While conventional sampling theory would dictate that such signals be sampled at the Nyquist rate (which could even be infinite for a stream of delta functions), Vetteri et al. have shown instead that signals can be recovered when sampled at the rate of innovation. The idea is that, rather than sampling the signal directly, it is preferable to sample a filtered version of the signal. From these samples, then, it is possible to write a system of equations that describe the unknown signal parameters. These can be solved using a variety of techniques; one technique involving eigendecomposition is also robust to noise. See I. Maravic and M. Vetterli, “Sampling and reconstruction of signals with finite innovation in the presence of noise,” IEEE Transactions on Signal Processing, Vol. 53, No. 8, pp. 2788-2805, 2005. Moreover, the computational complexity of the reconstruction techniques relate to the innovation rate R and not the Nyquist frequency.
The primary limitation of such an approach is that it pertains only to a limited class of signals. To date, the examples provided in the literature are essentially limited to delta sequences, splines, piecewise polynomials, and pulse trains. However, there may also be many interesting sparse signals that are not well-modeled with such a parameterization. One example is an arbitrary piecewise smooth signal, which is sparse in the wavelet domain but not easily expressed in parametric form.
1.3.4 AM-FM Energy Detection and Separation
In J. F. Kaiser, “On a simple algorithm to calculate the energy of a signal,” Proc. IEEE ICASSP, Albuquerque, N. Mex., April 1990, Kaiser proposed the use of a nonlinear operator, called Teager's Algorithm, to estimate the measure of the energy in a sinusoidal signal
                    s        =                ⁢                              a            ⁡                          (              t              )                                ⁢                      cos            ⁡                          [                              ϕ                ⁡                                  (                  t                  )                                            ]                                ⁢                      :                    ⁢                      Φ            ⁡                          (              s              )                                                                        =                    ⁢                                                                                          ⅆ                    2                                    ⁢                  s                                                  ⅆ                                      t                    2                                                              -                              s                ⁢                                                      ⅆ                    s                                                        ⅆ                    t                                                                        ≈                                                            a                  2                                ⁡                                  (                  t                  )                                            ⁢                                                w                  i                  2                                ⁡                                  (                  t                  )                                                                    ,            where wi=dφ/dt is the instantaneous frequency. This operator motivated an energy separation algorithm (ESA) that estimates the squared amplitude envelope and squared instantaneous frequency:
                    a        ^            2        ⁡          (      t      )        =                                          Φ            2                    ⁡                      (            s            )                                    Φ          ⁡                      (                                          ⅆ                s                                            ⅆ                t                                      )                              ⁢                          ⁢      and      ⁢                          ⁢                                    w            ^                    i          2                ⁡                  (          t          )                      =                            Φ          ⁢                                    ⅆ              s                                      ⅆ              t                                                Φ          ⁡                      (            s            )                              .      See P. Maragos, J. E Kaiser, and T. E Quatieri, “On amplitude and frequency demodulation using energy operators,” IEEE Trans. Signal Processing, 41(4):1532-1550, April 1993. The error bounds are small for the noiseless case with some general conditions. However, the presence of noise renders the operator Φ unpredictable, and thus the estimates become unreliable. In A. C. Bovik, P. Maragos, and T. E Quatieri, “AM-FM energy detection and separation in noise using multiband energy operators,” IEEE Trans. Signal Processing, 41(12):3245 3265, December 1993, Bovik et al. presented a modified algorithm with high tolerance to noise, designed for detection of AM and FM signals in noisy environments. In this algorithm, the signal is filtered through a bank of bandpass filters, and analyzed using the Φ operator and ESA algorithm at the channel with dominant local response. Since the operator Φ becomes negligible in cases when the instantaneous frequency falls outside the passband of a given filter, the filter containing the dominant signal frequency can be easily identified. By using the filterbank structure, the signal-to-noise ratio of the input signal is reduced by the bandpass filtering at the dominant filter element.
The algorithm has also been adapted to discrete time signals, but requires sampling at the Nyquist rate for the highest frequency required to be detected, i.e., only frequencies up to half the sampling rate can be detected using the discrete-time algorithm. See P. Maragos, J. F. Kaiser, and T. F. Quatieri, “Energy separation in signal modulation with application to speech analysis,” IEEE Trans. Signal Processing, 41(4):3024-3051, April 1993. The noise tolerance is dependent on the bandwidth of each of the filters in the filterbank, and thus dependent on the number of filters. These two considerations restrict the feasibility of the approach in real-world AICs.